// 2025/09/08
// Author: Forever
#include <bits/stdc++.h>
using namespace std;

int n, m, dis[51][51];
bool dp[51][51][65];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        dp[x][y][0] = true, dis[x][y] = 1;
    }
    for (int k = 1; k <= 64; k++)
        for (int t = 1; t <= n; t++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (dp[i][t][k - 1] && dp[t][j][k - 1])
                        dp[i][j][k] = true, dis[i][j] = 1;
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dis[i][k] + dis[k][j] < dis[i][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
    cout << dis[1][n] << endl;
    return 0;
}